package main.java;

/**
 * @program: pratice
 * @author: 关键我是大怪
 * @create: 2021-10-01 19:16
 */

/**
 * 题目：
 * 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），
 * 可知至少存在一个重复的整数。
 * 假设 nums 只有 一个重复的整数 ，找出这个重复的数 。
 * <p>
 * 思路 ：当成存在环的链表，使用快慢指针来做
 */
public class Test36_寻找重复数 {
    public int findDuplicate(int[] nums) {
        int fast = 0;
        int slow = 0;
        while (true) {
            fast = nums[nums[fast]];
            slow = nums[slow];
            if (fast == slow) {
                break;
            }
        }
        fast = 0;
        while (fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
        }
        return fast;
    }
}
